package oj.oj_142;

import oj.ListNode;

/**
 * 环形链表 II
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (true) {
            if (fast == null) {
                break;
            }
            fast = fast.next;
            slow = slow.next;
            if (fast == null) {
                break;
            }
            fast = fast.next;

            if (fast == slow) {
                break;
            }
        }

        // fast == null || fast == slow
        // fast == null : 链表不带环
        // fast == slow : 链表带环
        if (fast == null) {
            return null;
        }

        // fast == slow 相等，都指向相遇点
        ListNode c1 = head;
        ListNode c2 = fast;

        while (c1 != c2) {
            c1 = c1.next;
            c2 = c2.next;
        }

        return c1;
    }
}
